package d2_final_exam.d6_sixth_question;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MyLinkedList02<E extends Comparable> {
    // 封装一个链表
    Node<E> head = null;

    /**
     * 定义了一个私有的内部类，作为链表的结点。
     */
    public static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public Node<E> add(E e) {
        if (head == null) {
            head = new Node(e, null);
        } else {
            // 往后面插入结点。（尾插法）
            Node<E> temp = head;
            // 让temp走到尾部结点
            while (temp.next != null) {
                temp = temp.next;
            }
            // 把当前结点创建出来，加入到尾部结点
            temp.next = new Node(e, null);
        }
        return head;
    }

    //1、首先开发一个排序的方法,每个对象已经封装了head,不许要传节点进来
    public Node<E> sorted() {
        //1.极端判断
        if (head == null) {
            return null;
        }
        //2.准备一个集合
        List<E> number = new ArrayList<>();
        //3.用一个临时节点,记录头节点-->保护头节点
        Node<E> temp = head;
        //4.循环将节点的数据存入的集合中
        while (temp != null) {
            number.add(temp.data);
            //5.让节点往下挪
            temp = temp.next;
        }
        //6.对集合进行性排序
        Collections.sort(number);//不知道你的排序规则 --->让这个泛型继承排序的规则类

        //7.再次用一个临时节点,记录头节点
        Node<E> temp2 = head;
        //8.遍历集合,将排好序的集合中的数据存储到链表中
        for (E e : number) {
            temp2.data = e;
            temp2 = temp2.next;
        }
        return head;
    }

    //2、开发一个遍历链表的方法
    //为了可以遍历,后面的合并链表的节点,最后是接收一下,要遍历链表的头节点
    public void forEach(Node<E> head) {
        //1.首先最极端判断
        if (head == null) {
            System.out.println(head);
            return;
        }
        //2.记录临时节点
        Node<E> temp = head;
        //3.顺着节点往下找,将元素打印出来
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }

        System.out.println();//进行换行
    }

    //3、开发一个方法,接受另外一个链表的头节点,然后进行拼接成一个新的链表
    public Node<E> mergeSort(Node<E> head2) {
        //1.进行极端判断 -->不进行拼接的情况
        if (head2 == null && head == null) {
            return null;
        }

        if (head == null && head2 != null) {
            return head2;
        }

        if (head != null && head2 == null) {
            return head;
        }
        /*if (head != null || head2 != null){
            //可以开始拼接了
            //有一个投机取巧的方法---> 就是将两个链表一接,然后调用上年的排序方法,最后返回出去接口
            //1.首先定义一个临时节点,用于记录头节点
            Node<E> temp = head;
            //2.开始遍历
            while(temp.next != null){
                temp = temp.next;
            }
            //3.当来到这的时候temp,就是最后一个节点了
            //直接接起来
            temp.next = head2;

            //然后调用sort()方法
//            Node<E> sorted = ;
        }
            return sorted();*/

        //老师的方法-------->使用双指针的方法
        if (head != null && head2 != null) {
            // head = 1 2 3
            //          temp1
            //head2 = 1 2 3 4 5 6
            //          temp2
            //思想就是让两个指针进行比较,小的就添加到新链表中,然后往后移
            //1.定义两个指针分别记录两个链表的头节点
            Node<E> temp1 = head;
            Node<E> temp2 = head2;
            //3.创建一个新的链表
            Node<E> newNode = new Node<>(null, null);//由于要将节点拼接起来,所以要初始化节点,相当于一个占位节点
            Node<E> temp = newNode;
            //2.然后开始遍历
            while (temp1 != null && temp2 != null) {
                //4.开始比较
//                if (temp1.data < temp2.data){}------->无法实现比较,就是用方法,官方能比较,我们也可以,继承了Comparable
                //return (x < y) ? -1 : ((x == y) ? 0 : 1); ---->两个数进行比较, x < y -1
                //                                                            x == y 0
                //                                                            x > y 1
                if (temp1.data.compareTo(temp2.data) == -1) {
                    //5.将小的赋值给新链表
//                   newNode.data = temp1.data;
                    newNode.next = temp1;
                    //6.让temp1往后移动

                    temp1 = temp1.next;
                } else {
                    newNode.next = temp2;
                    temp2 = temp2.next;

                }
                //每次添加完成数据之后,新链表要进行向后移动
                newNode = newNode.next;

            }

            //7.判断哪个想到null
            if (temp1 == null) {
                //直接进行凭借
                newNode.next = temp2;
            }
            if (temp2 == null) {
                newNode.next = temp1;
            }
            head = temp.next;//这一步将头节点去掉,真的是精妙
//                forEach(head);
//            return newNode;
        }
//        System.out.println(head);
//        forEach(head);
        return head;
    }
}